package dynamic;

import java.util.Arrays;

public class LongestPalindromeSubsequence {
    public String findLength(String A) {
        String B = "";
        for (int i = A.length() - 1; i >= 0; i--) {
            B += A.charAt(i);
        }
        String[][] c = new String[A.length() + 1][A.length() + 1];
        String lenth = "";
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[i].length; j++) {
                c[i][j] = "";
            }
        }
        for (int i = 1; i < A.length() + 1; i++) {
            for (int j = 1; j < B.length() + 1; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + A.charAt(i - 1);
                }
                if (lenth.length() < c[i][j].length())
                    lenth = c[i][j];
            }
        }
        return lenth;
    }


}
